package com.zzy.sort;

/*215. 数组中的第 K 个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:输入: [3,2,1,5,6,4], k = 2输出: 5
示例 2:输入: [3,2,3,1,2,4,5,5,6], k = 4输出: 4*/
public class LC215FindKthLargest {
    //////////////////////选择排序//////////////////////////
    public static int findKthLargest(int[] nums, int k) {

        for (int i = 0; i < k; i++) {
            int largestIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > nums[largestIndex]) {
                    largestIndex = j;
                }
            }
            exch(nums, i, largestIndex);
        }
        return nums[k - 1];
    }

    public static void exch(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //////////////////////堆排序//////////////////////////
    public static int findKthLargest1(int[] nums, int k) {
        buildMaxHeap(nums);
        for (int i = nums.length - 1; i > nums.length - 1 - k; i--) {
            exch(nums, 0, i);
            maxHeapify(nums, 0, i);
        }

        return nums[nums.length - k];
    }

    private static void buildMaxHeap(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            maxHeapify(arr, i, arr.length);
        }
    }

    private static void maxHeapify(int[] arr, int parentIndex, int heapSize) {
        int lChild = 2 * parentIndex + 1;
        int rChild = lChild + 1;
        int largestIndex = parentIndex;
        if (lChild < heapSize && arr[lChild] > arr[largestIndex]) {
            largestIndex = lChild;
        }
        if (rChild < heapSize && arr[rChild] > arr[largestIndex]) {
            largestIndex = rChild;
        }
        if (largestIndex != parentIndex) {
            exch(arr, parentIndex, largestIndex);
            maxHeapify(arr, largestIndex, heapSize);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6};
        int k = 4;
        System.out.println(findKthLargest(nums, k));
        System.out.println(findKthLargest1(nums, k));
    }
}
